#include <iostream>

using namespace std;

// 方法一：从头到尾遍历数组O(n2)
// 方法二：双指针遍历数组
void reorderArrayFunTwo(int * data, int length ){
	if ( data == nullptr || length <=0 )
		return;
    int * start = data;
    int * end = data + length -1;
    while ( start != end ){
        while ( start < end && *start%2 == 1 ){
            start ++;
        }
        while ( start < end && *end % 2 == 0 ){
            end --;
        }

        if ( start < end ){
            int tmp = *start;
            *start = *end;
            *end = tmp;
        }
    }
}

// 方法三：实现一个模板，可以解决此类问题, 采用函数指针实现

void reorder(int * data, int length, bool (*func)(int)){
    if ( data == nullptr || length <=0 )
		return;
    int * start = data;
    int * end = data + length -1;
    while ( start != end ){
        while ( start < end && !func(*start) ){
            start ++;
        }
        while ( start < end && func(*end) ){
            end --;
        }

        if ( start < end ){
            int tmp = *start;
            *start = *end;
            *end = tmp;
        }
    }
}

bool isEven(int key){
    // 位运算
    return ( key & 1) == 0;
}

// 判断是否为负数
bool isNegtive(int key){
	return key>=0;
}

void reorderArrayFunThree(int * data, int length){
    reorder(data, length, isEven);
    // 实现所有负数都在非负数前面
    reorder(data, length, isNegtive);
}

void printData(int *data, int length ){
    for ( int i = 0; i< length; i++ ) {
        cout << *(data+i) << endl;
    }
}

int main(void){
    // Test1
    int numbers[] = {2, 4, 6, 1, 3, 5, 7};
    int numbers[] = {2, -4, 6, -1, -3, -5, 7};
    reorderArrayFunTwo(numbers, sizeof(numbers)/sizeof(int));
    printData(numbers, sizeof(numbers)/sizeof(int));
    cout << "------" << endl;
    
    // Test2
    // 函数指针方式来实现该功能
    reorderArrayFunThree(numbers, sizeof(numbers)/sizeof(int));
    printData(numbers, sizeof(numbers)/sizeof(int));
    return 0;
}